Giả sử rằng < {\displaystyle \,<\,} là quan hệ hai ngôi thuần nhất trên tập hợp S {\displaystyle S} (tức là, < {\displaystyle \,<\,} là tập con của S × S {\displaystyle S\times S} ) và theo thông thường, được viết là x < y {\displaystyle x<y} và nói rằng x < y {\displaystyle x<y} được thoả mãn hoặc là đúng khi và chỉ khi ( x , y ) ∈ < . {\displaystyle (x,y)\in \,<.\,}

Thứ tự yếu nghiêm ngặt

Nhắc lại về tính không so sánh được và tính chất bắc cầu của tính không so sánh được

Hai phần tử x {\displaystyle x} và y {\displaystyle y} trên S {\displaystyle S} được gọi là không so sánh được với nhau tương ứng với < {\displaystyle \,<\,} nếu cả hai x < y  và  y < x {\displaystyle x<y{\text{ và }}y<x} đều không đúng.[1] Tính không so sánh được tương ứng với < {\displaystyle \,<\,} chính nó là quan hệ đối xứng và thuần nhất trên S {\displaystyle S} , quan hệ này có tính phản xạ khi và chỉ khi < {\displaystyle \,<\,} hoàn toàn không phản xạ (nghĩa là x < x {\displaystyle x<x} luôn sai), ta có thể giả định ý này sao cho tính chất bắt cầu là tính chất còn lại "quan hệ không so sánh được" cần có để trở thành quan hệ tương đương. Bên cạnh đó, định nghĩa quan hệ thuần nhất được cảm sinh ≲ {\displaystyle \,\lesssim \,} trên S {\displaystyle S} bằng cách định nghĩa

có một điểm quan trọng là, định nghĩa này không nhất thiết phải giống với: x ≲ y {\displaystyle x\lesssim y} khi và chỉ khi x < y  hoặc  x = y . {\displaystyle x<y{\text{ hoặc }}x=y.} Hai phần tử x , y ∈ S {\displaystyle x,y\in S} không so sánh được với nhau tương ứng với < {\displaystyle \,<\,} khi và chỉ khi x  và  y {\displaystyle x{\text{ và }}y} tương đương với nhau tương ứng với quan hệ ≲ {\displaystyle \,\lesssim \,} (nếu muốn ngắn dòng hơn, ≲ {\displaystyle \,\lesssim } -tương đương), thì theo định nghĩa, tức là cả hai x ≲ y  và  y ≲ x {\displaystyle x\lesssim y{\text{ và }}y\lesssim x} đều đúng. Quan hệ "không so sánh được với nhau tương ứng với < {\displaystyle \,<} " do đó giống hệt với (tức bằng với) quan hệ " ≲ {\displaystyle \,\lesssim } -tương đương với nhau" (do đó, quan hệ trước có tính bắc cầu khi và chỉ khi quan hệ sau có tính bắc cầu) Khi < {\displaystyle \,<\,} hoàn toàn không phản xạ thì "tính chất bắc cầu của tính không so sánh được" (định nghĩa bên dưới) là điều kiện duy nhất cần và đủ để đảm bảo quan hệ " ≲ {\displaystyle \,\lesssim } -tương đương với nhau" tạo thành quan hệ tương đương trên S . {\displaystyle S.} Nếu nó quả thật đúng, thì nó cho phép biến bất kỳ hai phần tử x , y ∈ S {\displaystyle x,y\in S} thoả mãn x ≲ y  và  y ≲ x {\displaystyle x\lesssim y{\text{ và }}y\lesssim x} về một (tức là chúng đồng nhất với nhau trong lớp tương đương của chúng).

Định nghĩa

Thứ tự yếu nghiêm ngặt trên tập hợp S {\displaystyle S} là quan hệ thứ tự riêng phần nghiêm ngặt < {\displaystyle \,<\,} trên S {\displaystyle S} trong đó quan hệ không so sánh được cảm sinh trên S {\displaystyle S} bởi < {\displaystyle \,<\,} là quan hệ bắc cầu.[1] Cụ thể, thứ tự yếu nghiêm ngặt trên S {\displaystyle S} là quan hệ thuần nhất < {\displaystyle \,<\,} trên S {\displaystyle S} thoả mãn bốn tính chất sau:

1. Tính hoàn toàn không phản xạ: Với mọi x ∈ S , {\displaystyle x\in S,} x < x {\displaystyle x<x} luôn sai.
   • Điều kiện này chỉ thoả mãn khi quan hệ cảm sinh ≲ {\displaystyle \,\lesssim \,} trên S {\displaystyle S} có tính phản xạ, trong đó ≲ {\displaystyle \,\lesssim \,} được định nghĩa x ≲ y {\displaystyle x\lesssim y} đúng khi và chỉ khi y < x {\displaystyle y<x} sai.
2. Tính bắc cầu: Với mọi x , y , z ∈ S , {\displaystyle x,y,z\in S,} nếu x < y  và  y < z {\displaystyle x<y{\text{ và }}y<z} thì x < z . {\displaystyle x<z.}
3. Tính bất đối xứng: Với mọi x , y ∈ S , {\displaystyle x,y\in S,} nếu x < y {\displaystyle x<y} đúng thì y < x {\displaystyle y<x} sai.
4. Tính chất bắc cầu của tính không so sánh được: Với mọi x , y , z ∈ S , {\displaystyle x,y,z\in S,} nếu x {\displaystyle x} không so sánh được với y {\displaystyle y} (tức là cả x < y {\displaystyle x<y} và y < x {\displaystyle y<x} đều sai) và nếu y {\displaystyle y} không so sánh được với z , {\displaystyle z,} thì x {\displaystyle x} cũng không so sánh được với z . {\displaystyle z.}
   • Hai phần tử x  và  y {\displaystyle x{\text{ và }}y} không so sánh được với nhau tương ứng với < {\displaystyle \,<\,} khi và chỉ khi chúng tương đương với nhau tương ứng với quan hệ cảm sinh ≲ {\displaystyle \,\lesssim \,} (theo định nghĩa, tức là cả x ≲ y  và  y ≲ x {\displaystyle x\lesssim y{\text{ và }}y\lesssim x} đều đúng), trong khi ngay trước đó, x ≲ y {\displaystyle x\lesssim y} đúng khi và chỉ khi y < x {\displaystyle y<x} sai. Do đó điều kiện này chỉ thoả mãn khi quan hệ đối xứng trên S {\displaystyle S} định nghĩa bởi " x  và  y {\displaystyle x{\text{ và }}y} tương đương với nhau tương ứng với ≲ {\displaystyle \,\lesssim \,} " có tính bắc cầu, nghĩa là mỗi khi cặp x  và  y {\displaystyle x{\text{ và }}y} ≲ {\displaystyle \,\lesssim } -tương đương với nhau và cặp y  và  z {\displaystyle y{\text{ và }}z} ≲ {\displaystyle \,\lesssim } -tương đương với nhau thì phải x  và  z {\displaystyle x{\text{ và }}z} ≲ {\displaystyle \,\lesssim } -tương đương với nhau. Ta cũng có thể phát biểu lại thành: Nếu x ≲ y  và  y ≲ x {\displaystyle x\lesssim y{\text{ và }}y\lesssim x} và đồng thời y ≲ z  và  z ≲ y {\displaystyle y\lesssim z{\text{ và }}z\lesssim y} thì phải x ≲ z  và  z ≲ x . {\displaystyle x\lesssim z{\text{ và }}z\lesssim x.}

Tính chất (1), (2), và (3) là các tính chất định nghĩa của thứ tự riêng phần nghiêm ngặt, mặc dù có một số phần thừa trong danh sách này là vì tính bất đối xứng (3) sẽ suy ra tính hoàn toàn không phản xạ (1), và cũng vì tính hoàn toàn không phản xạ (1) và tính bắc cầu (2) sẽ cùng suy ra tính bất đối xứng (3).[7] Quan hệ không so sánh được luôn luôn đối xứng và nó thêm tính phản xạ khi và chỉ khi < {\displaystyle \,<\,} là quan hệ hoàn toàn không phản xạ. Do đó, thứ tự riêng phần nghiêm ngặt < {\displaystyle \,<\,} là thứ tự yếu nghiêm ngặt khi chỉ khi quan hệ không so sánh được cảm sinh của nó là quan hệ tương đương.Trong trường hợp này, các lớp tương đương của nó phân hoạch tập S {\displaystyle S} và hơn nữa, tập P {\displaystyle {\mathcal {P}}} của các lớp tương đương này có thể sắp thứ tự toàn phần theo một quan hệ hai ngôi, cũng được ký hiệu < , {\displaystyle \,<,} được định nghĩa cho mọi A , B ∈ P {\displaystyle A,B\in {\mathcal {P}}} như sau:

A < B  khi và chỉ khi  a < b {\displaystyle A<B{\text{ khi và chỉ khi }}a<b} với một số (hoặc tương đương, tất cả) đại diện a ∈ A  và  b ∈ B . {\displaystyle a\in A{\text{ và }}b\in B.}

Ngược lại, bất kỳ thứ tự toàn phần nghiêm ngặt trên phân hoạch P {\displaystyle {\mathcal {P}}} của S {\displaystyle S} cảm sinh thứ tự yếu nghiêm ngặt < {\displaystyle \,<\,} trên S {\displaystyle S} định nghĩa bởi a < b {\displaystyle a<b} khi và chỉ khi tồn tại các tập hợp A , B ∈ P {\displaystyle A,B\in {\mathcal {P}}} trong phân hoạch sao cho a ∈ A , b ∈ B ,  và  A < B . {\displaystyle a\in A,b\in B,{\text{ và }}A<B.}

Không phải mọi quan hệ thứ tự riêng phần nghiêm ngặt đều thoả mãn tính bắc cầu của tính không so sánh được. Ví dụ chẳng hạn, xét quan hệ thứ tự riêng phần trên { a , b , c } {\displaystyle \{a,b,c\}} được nghĩa bởi b < c . {\displaystyle b<c.} Các cặp a , b  và  a , c {\displaystyle a,b{\text{ và }}a,c} không so sánh được với nhau nhưng b {\displaystyle b} và c {\displaystyle c} thì có quan hệ với nhau, do đó tính không so sánh được không phải quan hệ tương đương và ví dụ này không phải thứ tự yếu nghiêm ngặt.

Đối với tính bắc cầu của không so sánh được, các điều kiện sau là điều kiện cần, còn đối với quan hệ thứ tự một phần nghiêm ngặt thì chúng là điều kiện đủ:

• Nếu x < y {\displaystyle x<y} thì với mọi z , {\displaystyle z,} hoặc x < z  hoặc  z < y {\displaystyle x<z{\text{ hoặc }}z<y} hoặc cả hai.
• Nếu x {\displaystyle x} không so sánh được với y {\displaystyle y} thì với mọi z {\displaystyle z} , hoặc ( x < z  và  y < z {\displaystyle x<z{\text{ và }}y<z} ) hoặc ( z < x  và  z < y {\displaystyle z<x{\text{ và }}z<y} ) hoặc ( z {\displaystyle z} không so sánh được với x {\displaystyle x} và z {\displaystyle z} không so sánh được với y {\displaystyle y} ).

Tiền thứ tự toàn phần

Thứ tự yếu nghiêm ngặt có quan hệ rất gần gũi với tiền thứ tự toàn phần hay thứ tự yếu không nghiêm ngặt, và các khái niệm toán học có thể mô hình hoá bằng thứ tự yếu cũng có thể mô hình hoá bằng tiền thứ tự toàn phần. Tiền thứ tự toàn phần hay thứ tự yếu toàn phần là tiền thứ tự mà mọi cặp phần tử đều so sánh được với nhau.[8] Tiền thứ tự toàn phần ≲ {\displaystyle \,\lesssim \,} thoả mãn các tính chất sau:

• Tính bắc cầu: Với mọi x , y ,  và  z , {\displaystyle x,y,{\text{ và }}z,} nếu x ≲ y  và  y ≲ z {\displaystyle x\lesssim y{\text{ và }}y\lesssim z} thì x ≲ z . {\displaystyle x\lesssim z.}
• Tính liên thông mạnh: Với mọi x  và  y , {\displaystyle x{\text{ và }}y,} x ≲ y  hoặc  y ≲ x . {\displaystyle x\lesssim y{\text{ hoặc }}y\lesssim x.}
  • Suy ra tính phản xạ: với mọi x , {\displaystyle x,} x ≲ x . {\displaystyle x\lesssim x.}

Thứ tự toàn phần là tiền thứ tự có tính bất đối xứng, nói cách khác, nó là thứ tự riêng phần. Tiền thứ tự toàn phần đôi khi được gọi là quan hệ ưu tiên.

Bù của thứ tự yếu nghiêm ngặt là tiền thứ tự toàn phần và ngược lại, nhưng thường thì tự nhiên hơn khi liên hệ các thứ tự yếu nghiêm ngặt và tiền thứ tự toàn phần theo cách bảo toàn thứ tự các phần tử thay vì đổi hướng chúng. Do vậy, ta sẽ lấy ngược của phần bù: cho thứ tự yếu nghiêm ngặt < , {\displaystyle \,<,} định nghĩa tiền thứ tự toàn phần ≲ {\displaystyle \,\lesssim \,} bằng cách đặt x ≲ y {\displaystyle x\lesssim y} mỗi khi không y < x . {\displaystyle y<x.} Trong hướng ngược lại, để định nghĩa thứ tự yếu nghiêm ngặt < từ tiền thứ tự toàn phần ≲ , {\displaystyle \,\lesssim ,} đặt x < y {\displaystyle x<y} mỗi khi không y ≲ x . {\displaystyle y\lesssim x.} [9]

Trong bất kỳ tiền thứ tự, có quan hệ tương đương tương ứng trong đó mỗi hai phần tử x {\displaystyle x} và y {\displaystyle y} được gọi là tương đương với nhau nếu x ≲ y  và  y ≲ x . {\displaystyle x\lesssim y{\text{ và }}y\lesssim x.} Trong trường hợp của tiền thứ tự toàn phần, quan hệ thứ tự riêng phần tương ứng trên tập các lớp tương đương là quan hệ thứ tự toàn phần. Hai phần tử tương đương với nhau trong tiền thứ tự toàn phần khi và chỉ khi chúng không so sánh được với nhau trong thứ tự yếu tương ứng.

Phân hoạch được sắp

Phân hoạch của tập hợp S {\displaystyle S} là họ các tập con không giao nhau của S {\displaystyle S} có S {\displaystyle S} làm hợp của chúng. Một phân hoạch, khi đi kèm với thứ tự toàn phần thì sẽ hình thành nên một cấu trúc, tên gọi cấu trúc đó là phân hoạch được sắp được đưa bởi nhà toán học Richard P. Stanley[10], còn tên danh sách tập hợp được đưa bởi Theodore Motzkin.[11] Phân hoạch được sắp của một tập hữu hạn có thể viết thành dãy hữu hạn của các tập của phần hoạch, ví dụ chẳng hạn, ba phân hoạch được sắp của tập { a , b } {\displaystyle \{a,b\}} là

Trong thứ tự yếu nghiêm ngặt, các lớp tương đương của quan hệ không so sánh được sinh ra phân hoạch tập hợp, trong đó các tập hợp này thừa hưởng thứ tự toàn phần từ các phần tử của chúng, từ đó sinh ra phân hoạch được sắp. Theo hướng ngược lại cũng tương tự như vậy, bất kỳ phân hoach được sắp sẽ cảm sinh thứ tự yếu nghiêm ngặt trong đó hai phần tử không so sánh được với nhau khi chúng nằm trong cùng một tập của phân hoạch còn nếu không thì theo thứ tự của các tập chứa nó.

Biểu diễn bằng hàm số

Đối với các tập có số lực lượng đủ nhỏ, có cách hình thức hoá thứ ba dựa trên các hàm thực. Nếu X {\displaystyle X} là một tập hợp bất kỳ và ta có hàm thực f : X → R {\displaystyle f:X\to \mathbb {R} } trên X {\displaystyle X} cảm sinh thứ tự yếu trên X {\displaystyle X} bằng cách đặt

Tiền thứ tự toàn phần được định nghĩa bằng cách đặt a ≲ b  khi và chỉ khi  f ( a ) ≤ f ( b ) {\displaystyle a{}\lesssim {}b{\text{ khi và chỉ khi }}f(a)\leq f(b)} còn quan hệ tương đương tương ứng được định nghĩa bằng cách đặt a ∼ b  khi và chỉ khi  f ( a ) = f ( b ) . {\displaystyle a{}\sim {}b{\text{ khi và chỉ khi }}f(a)=f(b).}

Các quan hệ không đổi khi f {\displaystyle f} được thay bằng g ∘ f {\displaystyle g\circ f} (hợp của hai hàm), trong đó g {\displaystyle g} là hàm thực tăng đơn điệu được định nghĩa trên miền giá trị của f . {\displaystyle f.} Do đó, từ hàm thoả dụng sẽ định nghĩa ra quan hệ ưu tiên. Trong ngữ cảnh đó, tiền thứ tự yếu còn được gọi là sắp xếp ưu tiên.[12]

Nếu X {\displaystyle X} hữu hạn hoặc đếm được, thì mọi thứ tự yếu trên X {\displaystyle X} có thể biểu diễn theo hàm số bằng cách này.[13] Tuy nhiên, tồn tại các thứ tự yếu nghiêm ngặt không có hàm thực tương ứng. Ví dụ chẳng hạn, không có hàm nào cho thứ tự từ điển trên R n . {\displaystyle \mathbb {R} ^{n}.} Do đó, mặc dù hầu như mọi quan hệ ưu tiên mô hình quan hệ đều định nghĩa hàm thoả dụng xê xích các phép biến đổi bảo toàn thứ tự, không có hàm nào cho ưu tiên thứ tự từ điển.

Tổng quát hơn, nếu X {\displaystyle X} là tập hợp, Y {\displaystyle Y} là tập đi kèm thứ tự yếu nghiêm ngặt < , {\displaystyle \,<,\,} và f : X → Y {\displaystyle f:X\to Y} là hàm số, thì f {\displaystyle f} cảm sinh thứ tự yếu trên X {\displaystyle X} bằng cách đặt

Như bên trên, ta sẽ có tiền thứ tự toàn phần định nghĩa bởi a ≲ b  khi và chỉ khi  f ( a ) ≲ f ( b ) , {\displaystyle a{}\lesssim {}b{\text{ khi và chỉ khi }}f(a){}\lesssim {}f(b),} và quan hệ tương đương tương ứng bằng cách đặt a ∼ b  khi và chỉ khi  f ( a ) ∼ f ( b ) . {\displaystyle a{}\sim {}b{\text{ khi và chỉ khi }}f(a){}\sim {}f(b).} Vì không giả định rằng f {\displaystyle f} là đơn ánh, nên một lớp chứa hai phần tương đương nhau trên Y {\displaystyle Y} có thể cảm sinh lớp lớn hơn trên X . {\displaystyle X.} Bên cạnh đó, f {\displaystyle f} cũng không nhất thiết phải là toàn ánh, nên một lớp của Y {\displaystyle Y} có thể có lớp nhỏ hơn hoặc rỗng trên X . {\displaystyle X.} Tuy nhiên, f {\displaystyle f} cảm sinh hàm đơn ánh ánh xạ các phân hoạch trên X {\displaystyle X} sang trên Y . {\displaystyle Y.} Do đó, trong trường hợp số phân hoạch hữu hạn, số các lớp trong X {\displaystyle X} nhỏ hơn hoặc bằng với số các lớp trên Y . {\displaystyle Y.}